#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <string>
#include <assert.h>
#include <stack>
using namespace std;
class Solution {
public:
	int operatorPrecedence(char ch)
	{
		struct opPD
		{
			char _op;
			int _pd;
		};
		static opPD arr[] = { {'+',1},{'-',1},{'*',2},{'/',2} };
		for (auto& e : arr)
		{
			if (e._op == ch)
			{
				return e._pd;
			}
		}
		//代码是不会走到这的,所以给个断言,断言生效,说明传值错误
		assert(false);
		return -1;
	}
	//中缀转后缀
	//遇到括号需要递归,所有i是控制递归的层数,然后将结果保存的s里面
	void toRPN(const string& s, size_t& i, vector<string>& v)
	{
		stack<char> st;
		while (i < s.size())
		{
			//首先判断是操作符还是操作数
			if (isdigit(s[i]))
			{
				//操作数
				string num;
				while (i < s.size() && isdigit(s[i]))
				{
					num += s[i];
					++i;
				}
				v.push_back(num);
			}
			else if (s[i] == '(')
			{
				//子表达式,递归处理即可
				i++;//过滤'('
				toRPN(s, i, v);
				
			}
			else if (s[i] == ')')
			{
				i++;//过滤')'
				//循环出栈,人vector
				while (!st.empty())
				{
					v.push_back(string(1, st.top()));
					st.pop();
				}
				return;
			}
			else
			{
				//操作符
				if (st.empty() || operatorPrecedence(s[i]) > operatorPrecedence(st.top()))
				{
					st.push(s[i]);
					++i;
				}
				else
				{
					char op = st.top();
					st.pop();
					v.push_back(string(1,op));
				}
			}
		}
		while (!st.empty())
		{
			v.push_back(string(1, st.top()));
			st.pop();
		}
	}
};
int main()
{
	size_t i = 0;
	vector<string> v;
	//string str = "1+2-3";
	string str = "1+2-(3*4+5)-7";
	Solution().toRPN(str,i,v);
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}
